#ifndef ILLIB_ALLOCATOR_H_
#define ILLIB_ALLOCATOR_H_

#include <stddef.h>
#include <illib/CodeGenerator.h>
#include <illib/BasicLinkedList.h>
#include <illib/BasicRedBlackTree.h>
#include <illib/Log.h>
#include <illib/Exception.h>
#include <illib/System.h>
#include <new>

namespace illib{
	class Allocator : public CodeGenerator::Debuggable{
	private:
		Allocator(const Allocator &other);
		Allocator();
	protected:
		Allocator * parent_;
		size_t allocated_;
		virtual void allocated(size_t size);
		virtual void released(size_t size);
	public:
		virtual uint8_t* allocate(size_t requestedSize, size_t &allocatedSize) = 0;
		virtual bool release(void * ptr) = 0;
		virtual ~Allocator();
		virtual void * data(){
			return 0;
		}
		Allocator * parent();
		void parent(Allocator *parent);
		Allocator(Allocator * parent);
		virtual const char * name() = 0;
		Allocator * root();
	};

	namespace MemoryTracker {
		class MemoryTree : public BasicRedBlackTree::Tree {
		private:
			MemoryTree(const MemoryTree &other);
		public:
			MemoryTree();
		};
		class MemoryTreeFunctions : public BasicRedBlackTree::TreeFunctions{
		public:
			virtual bool lesser(BasicRedBlackTree::Node &left, BasicRedBlackTree::Node &right);
			virtual bool greater(BasicRedBlackTree::Node &left, BasicRedBlackTree::Node &right);
			virtual bool equal(BasicRedBlackTree::Node &left, BasicRedBlackTree::Node &right);
		};
		class Tracked : public BasicRedBlackTree::Node, public System::Memory {
		private:
			Tracked(const Tracked &other);
			Tracked();
		protected:
			Allocator * allocator_;
			Tracked(uint8_t* block, size_t blockSize, Allocator * allocator);
		public:
			virtual ~Tracked();
			virtual Allocator * allocator();
			virtual size_t allocated() = 0;
			virtual const char * name() = 0;
		};
		class DummyTracked : public Tracked{
		private:
			DummyTracked(const DummyTracked &other);
			DummyTracked();
		public:
			DummyTracked(uint8_t * ptr, size_t size);
			virtual size_t allocated();
			virtual const char * name();
			virtual ~DummyTracked();
		};
		class Tracker{
		private:
			Tracker(const Tracker &other);
		protected:
			MemoryTree tracked_;
			static Tracker * instance_;
			bool stackDirection_;
			friend Tracker & tracker();
			friend void tracker(Tracker & tracker);
		public:
			Tracker();
			Tracked * entry(void * ptr);
			bool stack(void * ptr);
			bool track(Tracked & memory);
			bool untrack(Tracked & memory);
			bool empty();
			bool release(void * ptr);
			size_t length();
		};
		extern Tracker & tracker();
		extern void tracker(Tracker & tracker);
	}
	namespace BlockAllocator{
		class BasicAllocator;
	};
	namespace PoolAllocator{
		class Pool : public MemoryTracker::Tracked, public Allocator{
		private:
			Pool(const Pool &other);
			Pool();
		protected:
			size_t itemSize_;
			uint8_t *data_;
			size_t used_;
			friend class BasicAllocator;
		public:
			Pool(uint8_t* block, size_t blockSize, size_t itemSize, uint8_t alignment, Allocator * parent);
			virtual ~Pool();
			virtual uint8_t* allocate(size_t requestedSize, size_t &allocatedSize);
			virtual bool release(void* ptr);
			virtual size_t allocated();
			void clear();
			bool contains(void* ptr);
			size_t used();
			size_t avaliable();
			size_t capacity();
			size_t mapsize();
			bool empty();
			bool full();
			static size_t calculateMemorySize(size_t itemSize, size_t itemCount, uint8_t alignment);
			static size_t calculateItemCount(size_t blockSize, size_t itemSize, uint8_t alignment);
			static size_t calculateMapSize(size_t blockSize, size_t itemSize, uint8_t alignment);
			virtual const char * name();
		};
		class ManagedPool;
		class BasicAllocator : public Allocator{
		private:
			BasicAllocator(const BasicAllocator &other);
			BasicAllocator();
		protected:
			size_t itemSize_;
			size_t poolSize_;
			BasicLinkedList::List pools_;
			uint8_t alignment_;
			ManagedPool& createPool();
			void destroyPool(ManagedPool & pool);
			friend class ManagedPool;
			friend class BlockAllocator::BasicAllocator;
		public:
			BasicAllocator(size_t itemSize, size_t poolSize, uint8_t alignment, Allocator * parent = 0);
			virtual ~BasicAllocator();
			virtual uint8_t* allocate(size_t requestedSize, size_t &allocatedSize);
			virtual bool release(void* ptr);
			void compact();
			void clear();
			size_t itemSize();
			size_t poolSize();
			virtual const char * name();
		};

		class ManagedPool : public Pool, public BasicLinkedList::Node {
		private:
			ManagedPool(const ManagedPool &other);
			ManagedPool();
		protected:
		public:
			ManagedPool(uint8_t* block, size_t blockSize, size_t itemSize, uint8_t alignment, BasicAllocator * parent);
			~ManagedPool();
			virtual const char * name();
		};
	}

	namespace BlockAllocator {
		class BasicAllocator;
		class SmallBlockPoolAllocator : public PoolAllocator::BasicAllocator, public BasicRedBlackTree::Node {
		private:
			SmallBlockPoolAllocator(const SmallBlockPoolAllocator &other);
			SmallBlockPoolAllocator();
		protected:
		public:
			SmallBlockPoolAllocator(size_t itemSize, size_t poolSize, uint8_t alignment, Allocator * parent);
			~SmallBlockPoolAllocator();
			virtual const char * name();
		};

		class LargeBlockTracker : public MemoryTracker::Tracked {
		private:
			LargeBlockTracker(const LargeBlockTracker &other);
			LargeBlockTracker();
		protected:
		public:
			LargeBlockTracker(uint8_t * block, size_t blockSize, Allocator * allocator);
			~LargeBlockTracker();
			virtual size_t allocated();
			virtual const char * name();
		};


		class SmallBlockPoolAllocatorSizeTree : public BasicRedBlackTree::Tree {
		private:
			SmallBlockPoolAllocatorSizeTree(const SmallBlockPoolAllocatorSizeTree &other);
		protected:

		public:
			SmallBlockPoolAllocatorSizeTree();
		};

		class SmallBlockPoolAllocatorSizeTreeFunctions : public BasicRedBlackTree::TreeFunctions {
		public:
			virtual bool lesser(BasicRedBlackTree::Node &left, BasicRedBlackTree::Node &right);
			virtual bool greater(BasicRedBlackTree::Node &left, BasicRedBlackTree::Node &right);
			virtual bool equal(BasicRedBlackTree::Node &left, BasicRedBlackTree::Node &right);
		};

		class LargeBlockSizeTree : public BasicRedBlackTree::Tree {
		private:
			LargeBlockSizeTree(const LargeBlockSizeTree &other);
		public:
			LargeBlockSizeTree();
		};

		class LargeBlockSizeTreeFunctions : public BasicRedBlackTree::TreeFunctions{
		public:
			virtual bool lesser(BasicRedBlackTree::Node &left, BasicRedBlackTree::Node &right);
			virtual bool greater(BasicRedBlackTree::Node &left, BasicRedBlackTree::Node &right);
			virtual bool equal(BasicRedBlackTree::Node &left, BasicRedBlackTree::Node &right);
		};

		class BasicAllocator : public Allocator{
		private:
			BasicAllocator(const BasicAllocator &other);
			BasicAllocator();
		protected:
			PoolAllocator::BasicAllocator smallBlockPoolAllocatorAllocator;
			PoolAllocator::BasicAllocator largeBlockTrackerAllocator;
			SmallBlockPoolAllocatorSizeTree smallBlockPoolAllocatorSizeTree_;
			LargeBlockSizeTree freeLargeBlockTrackers_;
			size_t maximumSmallBlockSize_;
			uint8_t alignment_;
			static const size_t minimumSmallBlockSize = 16;
			static const size_t smallBlockPoolAllocatorCount = 10;
			SmallBlockPoolAllocator& newSmallBlockPoolAllocator(size_t itemSize, size_t poolSize, uint8_t alignment);
			LargeBlockTracker & newLargeBlock(size_t requestedSize, size_t &allocatedSize, uint8_t alignment);
			void destroySmallBlockPoolAllocator(SmallBlockPoolAllocator& poolAllocator);
			void destroyLargeBlock(LargeBlockTracker& chunk);
			friend class PoolAllocator::BasicAllocator;
			friend class LargeBlockTracker;
		public:
			BasicAllocator(uint8_t alignment, Allocator * parent);
			virtual ~BasicAllocator();
			uint8_t* allocate(size_t requestedSize, size_t &size);
			virtual bool release(void* ptr);
			void compact();
			void clear();
			virtual const char * name();
			void debug(ConsoleLogger * parent);
		};
	}
}

#endif /* ILLIB_ALLOCATOR_H_ */
